package Subject;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 难度：简单
 * 
 * 387. 字符串中的第一个唯一字符
 * 	给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
 * 
 * 示例：
 * 	s = "leetcode"
 * 	返回 0
 * 	
 * 	s = "loveleetcode"
 * 	返回 2
 *
 * 提示：你可以假定该字符串只包含小写字母。
 *
 * */

public class FirstUniqChar {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FirstUniqChar fuc = new FirstUniqChar();
		System.out.println(fuc.firstUniqChar("loveleetcode"));
	}

	public int firstUniqChar(String s) {
		char[] charArray = s.toCharArray();
		for(char c:charArray) {
			if(s.indexOf(c) == s.lastIndexOf(c)) {
				return s.indexOf(c);
			}
		}
		return -1;
	}
	//方法一：使用哈希表存储频数
	public int firstUniqChar1(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
	//方法二：使用哈希表存储索引
	public int firstUniqChar2(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (position.containsKey(ch)) {
                position.put(ch, -1);
            } else {
                position.put(ch, i);
            }
        }
        int first = n;
        for (Map.Entry<Character, Integer> entry : position.entrySet()) {
            int pos = entry.getValue();
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        if (first == n) {
            first = -1;
        }
        return first;
    }
	//方法三：队列
	public int firstUniqChar3(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                position.put(ch, -1);
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().pos;
    }
    class Pair {
        char ch;
        int pos;

        Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }
    }
}
